#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;


	
int rBinarySearch(int sortedArray[], int first, int last, int key)
{
   
       int mid = (first + last) / 2;  // compute mid point.
	   cout<<"mid is "<< mid<< endl;
	   cout<<"first is "<< first<< endl;
	   cout<<"last is "<< last<< endl;
       if (key == sortedArray[mid]) 
	   {
		   return mid;   // found it.
	   }
       if (key < sortedArray[mid]) 
	   {
		   // Call ourself for the lower part of the array
           return rBinarySearch(sortedArray, first, mid-1, key);
	   }
       else
	   {
		   // Call ourself for the upper part of the array
           return rBinarySearch(sortedArray, mid+1, last, key);
	   }
   return -(first + 1);    // failed to find key
}


void main()
{
	int userInput;
	cout<<"please enter the number you are searching for!"<< endl;
	cin>> userInput;
	int x[10] = {1,4,5,7,8,9,19,21,32,34};
	int num = rBinarySearch(x, 0, 9, userInput);
	cout << "Found key at position: " << num << endl;

	system("pause");
}
